﻿#include <iostream>

/**
 * 递归求解
 */
static const char* recurTakeCoins(const char* first, const char* second, int* numbers, const size_t numberCount, const int total)
{
    if (total == 0)
    {
        return second;
    }

    const char* winner;
    bool firstWinExists = false;
    for (int i = 0; i < numberCount; i++)
    {
        for (int j = 1; j <= numbers[i]; j++)
        {
            int origin = numbers[i];
            numbers[i] -= j;
            winner = recurTakeCoins(second, first, numbers, numberCount, total - j);
            numbers[i] = origin;
            if (strcmp(winner, first) == 0)
            {
                firstWinExists = true;
                break;
            }
        }

        if (firstWinExists)
            break;
    }

    return firstWinExists ? first : second;
}

/**
 * 给定一个非负数组，每一个值代表该位置上有几个铜板。a和b玩游戏，a先手，b后手，轮到某个人的时候，只能在一个位置上拿任意数量的铜板，但是不能不拿。谁最先把铜板拿完谁赢。假设a和b都极度聪明，请返回获胜者的名字。
 * 
 * 思路：
 * Nim博弈问题
 * 一方先让另外一方遇到：所有数字的xor和为0，则胜利。
 */
int main_takeCoinsToMakeOpponentLose()
//int main()
{
    char name1[100] = "Jim";
    char name2[100] = "Mike";
    int numbers[] = {2,2,2,3,4,2,3,};
    int numberCount = sizeof(numbers) / sizeof(int);

    int xorSum = numbers[0];
    for (int i = 1; i < numberCount; i++)
    {
        xorSum ^= numbers[i];
    }

    if (xorSum == 0)
    {
        printf("%s win\n", name2);
    }
    else
    {
        printf("%s win\n", name1);
    }

    int total = 0;
    for (int i = 0; i < numberCount; i++)
    {
        total += numbers[i];
    }

    auto winner = recurTakeCoins(name1, name2, numbers, numberCount, total);
    printf("%s win by recur\n", winner);

    return 0;
}